import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution1 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>() ;
        char[] nums = s.toCharArray() ;
        HashMap<String , Integer> map = new HashMap<>() ;
        for(String str : words){
            map.put(str , map.getOrDefault(str , 0)+1);
        }
        ;
        int wordLen = words[0].length() ;
        int wordSum = wordLen * words.length ;
        HashMap<String , Integer> sum = new HashMap<>() ;
        for(int i = 0 ; i < wordLen ; i ++){
            int count = 0 ;
            for(int left = i , right=i ; right+wordLen <= nums.length ; right +=wordLen ){
                String str = new String(nums , right , wordLen);
                if(sum.getOrDefault(str,0) < map.getOrDefault(str,0)){
                    count ++ ;
                }
                sum.put(str,sum.getOrDefault(str,0)+1);
                while(right-left+1 > wordSum){
                    str = new String(nums , left , wordLen);
                    if(map.getOrDefault(str,0)>0 && sum.getOrDefault(str,0)<=map.getOrDefault(str,0)){
                        count --;
                    }
                    sum.put(str , sum.getOrDefault(str,0)-1);
                    left += wordLen;
                }
                if(count == words.length){
                    list.add(left);
                }
            }
            for (String tmp : words){
                sum.put(tmp,0);
            }
        }
        return list ;
    }
}